package com.zy.algorithm.v2;

import com.zy.algorithm.v2.bean.RadixSimpleNode;
import com.zy.utils.DataBuildUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RadixSortUtils {

    private static final Map<Integer, String> desMap = new HashMap<>();

    static {
        desMap.put(1, "个位");
        desMap.put(10, "十位");
        desMap.put(100, "百位");
        desMap.put(1000, "千位");
        desMap.put(10000, "万位");
    }


    /*
     * 获取数组a中最大值
     *
     * 参数说明：
     *     a -- 数组

     */
    static int get_max(int[] a) {
        int i, max;

        max = a[0];
        for (i = 1; i < a.length; i++)
            if (a[i] > max) max = a[i];
        return max;
    }

    /*
     * 对数组按照"某个位数"进行排序(桶排序)
     *
     * 参数说明：
     *     a -- 数组
     *     n -- 数组长度
     *     exp -- 指数。对数组a按照该指数进行排序。
     *
     * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；
     *    (01) 当exp=1表示按照"个位"对数组a进行排序
     *    (02) 当exp=10表示按照"十位"对数组a进行排序
     *    (03) 当exp=100表示按照"百位"对数组a进行排序
     *    ...
     */
    static void count_sort(List<RadixSimpleNode> stepList, int[] sort, int exp, int range) {
        int length = sort.length;
        int[] output = new int[length];             // 存储"被排序数据"的临时数组
        int i;
        int[] buckets = new int[10];

        // 将数据出现的次数存储在buckets[]中
        for (i = 0; i < length; i++) {
            buckets[(sort[i] / exp) % 10]++;


            RadixSimpleNode simpleNode = new RadixSimpleNode(exp);
            simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            simpleNode.setAssist(Arrays.copyOf(buckets, buckets.length));
            simpleNode.addOpIndex(i);
            simpleNode.setDes("大小:" + sort.length + " 范围:[0," + range + "] 基数:" + desMap.get(exp));
            stepList.add(simpleNode);
        }

        // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
        for (i = 1; i < 10; i++) {
            buckets[i] += buckets[i - 1];

            RadixSimpleNode simpleNode = new RadixSimpleNode(exp);
            simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            simpleNode.setAssist(Arrays.copyOf(buckets, buckets.length));
            simpleNode.addOpIndex(i);
            simpleNode.setDes("大小:" + sort.length + " 范围:[0," + range + "] 基数:" + desMap.get(exp));
            stepList.add(simpleNode);
        }

        // 将数据存储到临时数组output[]中
        for (i = length - 1; i >= 0; i--) {
            int sortedIndex = buckets[(sort[i] / exp) % 10] - 1;
            output[sortedIndex] = sort[i];
            buckets[(sort[i] / exp) % 10]--;

            sort[i] = 0;

            RadixSimpleNode simpleNode = new RadixSimpleNode(exp);
            simpleNode.setStepEnd(Arrays.copyOf(sort, sort.length));
            simpleNode.setSortedS(Arrays.copyOf(output, output.length));
            simpleNode.setAssist(Arrays.copyOf(buckets, buckets.length));
            simpleNode.addOpIndex(i - 1);
            simpleNode.addSortedIndex(sortedIndex);
            simpleNode.setDes("大小:" + sort.length + " 范围:[0," + range + "] 基数:" + desMap.get(exp));
            stepList.add(simpleNode);
        }

        // 将排序好的数据赋值给a[]
        for (i = 0; i < length; i++)
            sort[i] = output[i];
    }

    /*
     * 基数排序
     *
     * 参数说明：
     *     a -- 数组
     *     n -- 数组长度
     */
    public static void radix_sort(List<RadixSimpleNode> stepList, int[] a, int range) {
        int exp;    // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
        int max = get_max(a);    // 数组a中的最大值

        // 从个位开始，对数组a按"指数"进行排序
        for (exp = 1; max / exp > 0; exp *= 10)
            count_sort(stepList, a, exp, range);
    }


    public static List<RadixSimpleNode> radix_sort(int size, int range) {
        int[] array = DataBuildUtils.getRandomSortArray(size, range);
        List<RadixSimpleNode> stepList = new ArrayList<>();

        radix_sort(stepList, array, range - 1);
        return stepList;
    }
}
